package com.code.test.first.stack;

import java.util.Stack;

/**
 * https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0020.%E6%9C%89%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7.md
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
 * <p>
 * 有效字符串需满足：
 * <p>
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 注意空字符串可被认为是有效字符串。
 * 示例 1:
 * <p>
 * 输入: "()"
 * 输出: true
 * 示例 2:
 * <p>
 * 输入: "()[]{}"
 * 输出: true
 * 示例 3:
 * <p>
 * 输入: "(]"
 * 输出: false
 * 示例 4:
 * <p>
 * 输入: "([)]"
 * 输出: false
 */
public class Code20 {

    public static void main(String[] args) {
        String input = "({[]})";
        boolean valid= isValid(input);
        System.out.println(valid);

    }

    public static boolean isValid(String input) {
        Stack<Character> deque = new Stack<>();
        char ch;
        for (int i = 0; i < input.length(); i++) {
            ch = input.charAt(i);
            if (ch == '(') {
                deque.push(')');
            } else if (ch == '[') {
                deque.push(']');
            } else if (ch == '{') {
                deque.push('}');
            } else if (deque.isEmpty() || deque.peek() != ch) {
                /**
                 * 情况1：
                 * 如果都没有左括号了，此时都是右括号，那就开始匹配这个有括号与栈顶是否相等
                 * 与栈顶不相等，则代表不匹配
                 * 情况2：
                 * 如果都没有左括号了，但是此时栈都空了，没有匹配的字符，则代表右括号（因为前面都是左括号，这里是到了右括号）  没有找到左括号
                 */
                return false;
            } else {
                deque.pop();
            }
        }

        /**
         * 因为左括号是按顺序过来，但是右括号需要后进先出
         * 把左括号对应的右括号进栈，然后每次进来如果都是右括号，则直接与栈顶匹配是否相等，相等则出栈
         * 继续下一个
         */
        return deque.isEmpty();

    }


}
